#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>

void getNext(char* src, int* next)
{
	assert(src && next);
	next[0] = -1;
	if (strlen(src) == 1)
	{
		return;
	}
	next[1] = 0;
	int j = 2;
	int k = 0;
	while (j < strlen(src))
	{
		if (k == -1 || src[j - 1] == src[k])
		{
			if (src[j] == src[k + 1])
			{
				next[j] = next[k];
				j++;
				k++;
			}
			else
			{
				next[j] = k + 1;
				j++;
				k++;
			}
		}
		else
		{
			k = next[k];
		}
	}
}

int kmp(char* dest, char* src, int pos)
{
	int lens = strlen(src);
	int lend = strlen(dest);
	assert(lens && lend);
	assert(dest && src);
	assert(pos >= 0 && pos < lend);
	int i = pos;
	int j = 0;
	int* next = (int*)malloc(sizeof(int) * lens);
	assert(next);
	getNext(src, next);
	while (i < lend && j < lens)
	{
		if (j == -1 || dest[i] == src[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j == lens)
	{
		return i - j;
	}
	return -1;
}

int main()
{
	char* dest = "sdghaksjdh";
	char* src = "jd";
	int ret = kmp(dest, src, 2);
	printf("%d", ret);//2
	return 0;
}